As the role of computers has expanded, various different techniques have been developed for entering data into computers. One particularly useful technique for entering data is through the use of handwriting. By writing with a stylus or another object onto a digitizer to produce “electronic ink,” a computer user can forego the bulk and inconvenience associated with a conventional keyboard. Handwriting input conveniently may be used, for example, by doctors making rounds, architects on a building site, couriers delivering packages, warehouse workers walking around a warehouse, and in any situation when the use of a keyboard would be awkward or inconvenient.
While the possibility for entering handwritten input is more convenient than keyboard input in many situations, particularly for some computer users, text written in electronic ink typically cannot be directly manipulated by most software applications. Instead, text written in electronic ink typically must be analyzed and converted into another form, such as ASCII characters or other machine-generated or recognizable text or input. Analysis and conversion of this type include handwriting recognition processes, which recognize handwritten characters and convert them to machine-recognizable text, shapes, structures, or the like, e.g., based upon various relationships between individual electronic ink strokes making up the electronic ink input, such as the spatial and/or temporal relationships between individual ink strokes.
Handwriting recognition algorithms have improved dramatically in recent years, but their accuracy can be reduced under certain conditions, such as when electronic ink is written at an angle. Likewise, when separate groups of ink strokes cannot be easily distinguished, such as when two or more words are written closely together, many recognition algorithms will not accurately recognize the electronic ink. Some recognition algorithms also may incorrectly recognize electronic ink input as text when, in fact, the electronic ink was intended to be a drawing. For example, a user may annotate typewritten text, e.g., by writing an electronic ink stroke that underlines, highlights, circles, or crosses through some portion of the typewritten text. A handwriting recognition algorithm might then incorrectly recognize these annotation strokes as a dash, the number zero, the letter “O,” the letter “T,” or the like.
The accuracy of many recognition algorithms can be greatly improved by “parsing” (e.g., by analyzing the layout of and/or “classifying”) the electronic ink before sending the data through the handwriting recognition algorithm. A “classification” process typically determines whether an individual electronic ink stroke is part of a drawing (that is, a drawing ink stroke), part of handwritten text (that is, a text ink stroke), or some other special symbol (e.g., a mathematical symbol, a music symbol, a basic shape, other known symbols, etc.). Classification algorithms for identifying a wide variety of different symbols or stroke types are possible. A “layout analysis” process typically groups electronic ink strokes into meaningful associations, such as words, lines, paragraphs, etc. Layout analysis and classification processes thus may be used to identify which strokes in a collection of electronic ink belong to a single word, which words of the electronic ink are associated with a single line of text written in electronic ink, which lines of text written in the electronic ink are associated with a paragraph, which strokes are part of a drawing, music, mathematical equations, etc.
In order to prevent long “down” times or delays when the computer processor is not available to accept ink or other user input, electronic ink parsing, recognition, and/or other processing may be performed in an “incremental” manner, optionally while electronic ink and/or other data continues being entered into an electronic document. This processing also may be performed in a background thread while a user continues entering data, including electronic ink data, into a document, so that the user experiences minimal processing delays.
In some instances or application programs that handle electronic ink data, a user or application program may wish to know or determine what strokes, words, lines, and/or blocks of electronic ink or other data are located physically close to (i.e., spatially “neighboring”) other strokes, words, lines, and/or blocks of electronic ink or other data. Because of the dynamic and incremental nature of electronic ink input and/or its processing (e.g., via continued ink entry, via cut or paste operations, delete operations, via new downloads, etc.), the spatial relationships and the “neighborhood” of an ink stroke or collection of ink strokes (or other data) can change dramatically and quickly over time. Complete reparsing and/or re-determination of “neighborhood” data every time a parser changes an electronic ink data structure and/or every time “neighborhood” information is requested would result in very long processing times and very long processing delays. These long processing times and delays would frustrate computer users and/or render such systems unacceptably slow.
Accordingly, there is a need for electronic ink processing techniques that enable fast neighborhood determinations in dynamic electronic ink and/or other data processing environments.